# 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。
# 你不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
#
#  如果你能使这个正方形，则返回 true ，否则返回 false 。
#
#  示例 1:
# 输入: matchsticks = [1,1,2,2,2]
# 输出: true
# 解释: 能拼成一个边长为2的正方形，每边两根火柴。
#
#  示例 2:
# 输入: matchsticks = [3,3,3,3,4]
# 输出: false
# 解释: 不能用所有火柴拼成一个正方形。
from typing import List


class Solution:
    def makesquare2(self, matchsticks: List[int]) -> bool:
        """
        回溯法
        首先判断一下是否可能组成正方形，下面的情况均不可能组成正方形：
            1：n个火柴棍长度总和对4取余不为0 sum(matchsticks) % 4 != 0
            2：火柴的根数 len(matchsticks) < 4
            3：存在某根火柴长度 matchsticks[i] > sum(matchsticks) / 4

        火柴杆从大到小排序，先尝试大的减少回溯可能
        将每个火柴尝试丢入四个桶中，找到一个可以拼成正方形的组合就返回true
        遍历完如果尝试完所有可能还是不能完成正方形的拼接就返回false

        剪枝思路:
            每次放置时，每条边上不可放置超过总和1/4的火柴棍
        :param matchsticks:
        :return:
        """
        s = sum(matchsticks)
        buckets = [0] * 4
        if len(matchsticks) < 4 or s % 4 != 0 or max(matchsticks) > (targetSideLength := s // 4):
            return False

        def backTrack(index: int) -> bool:
            if index == len(matchsticks):
                return buckets[0] == buckets[1] == buckets[2] == buckets[3] == targetSideLength
            for i in range(4):
                if buckets[i] + matchsticks[index] <= targetSideLength:  # 剪枝操作：每次放置时，每条边上不可放置超过总和1/4的火柴棍
                    buckets[i] += matchsticks[index]
                    if backTrack(index + 1):
                        return True
                    buckets[i] -= matchsticks[index]
            return False

        matchsticks.sort(reverse=True)  # 先将数组从大到小排序可以减少不必要的回溯次数
        return backTrack(0)

    def makesquare1(self, matchsticks: List[int]) -> bool:
        """
        解法一(超时)：
        位运算
        1.使用位运算构造出所有和为 targetSideLen 存储在 allPosCombination 中 这就是 候选边 的组合
        2.allPosCombination 两两合并
          如果 (validSubList[i] & validSubList[j] = 0) 说明 i j 两条边没有选择同样的火柴棍(按位与结果为0)可以代表两条可以满足条件且同时存在的边,
          将 (validSubList[i] | validSubList[j]) 加入 validHalf 集合中 存储着所有 满足一半结果 的情况
        3.validHalf 两两合并 如果存在 (validHalf[i] & validHalf[j] = 0 )返回 true 说明有四个满足条件的边 可组成 正方形 否则返回 false
        :param matchsticks:
        :return:
        """
        s = sum(matchsticks)
        if (matchstickNums := len(matchsticks)) < 4 or s % 4 != 0 or max(matchsticks) > (targetSideLen := s // 4):
            return False
        allPosCombination = []  # 存所有和是 targetSideLen 的组合
        # n 个火柴棍，每个有分配不分配两种情况，一共有 2^n 种，表示为二进制是 1(n 个 0), 1-2^n 各自代表一个子组合
        for i in range(1, 2 << matchstickNums):  # 查看某个组合是否满足和为 targetSideLen , 将满足条件的组合记录下来
            tmpSum = 0
            flag = True
            # for j in range(matchstickNums):
            #     if (i & (1 << j)) != 0:
            #         if tmpSum + matchsticks[j] <= targetSideLen:
            #             tmpSum += matchsticks[j]
            #         else:
            #             flag = False
            #             break
            for j in range(matchstickNums):
                if (i & (1 << j)) != 0:
                    tmpSum += matchsticks[j]
            if tmpSum == targetSideLen and flag:
                allPosCombination.append(i)

        # print(len(allPosCombination))
        validHalfSubCombination = []
        for i in range(len(allPosCombination)):  # 将满足条件的且两不相交的组合两两合并起来
            for j in range(i + 1, len(allPosCombination)):
                if allPosCombination[i] & allPosCombination[j] == 0:
                    validHalfSubCombination.append(allPosCombination[i] | allPosCombination[j])
        # print(len(validHalfSubCombination))
        for i in range(len(validHalfSubCombination)):  # 因为需要分四组所以要两两合并两次
            for j in range(i + 1, len(validHalfSubCombination)):
                if validHalfSubCombination[i] & validHalfSubCombination[j] == 0:
                    return True
        return False

    def makesquare(self, matchsticks: List[int]) -> bool:
        return self.makesquare2(matchsticks)


if __name__ == "__main__":
    # matchsticks = [1, 1, 2, 2, 2]
    # matchsticks = [3, 3, 3, 3, 4]
    # matchsticks = [10, 6, 5, 5, 5, 3, 3, 3, 2, 2, 2, 2]
    # matchsticks = [6, 6, 6, 6, 4, 2, 2]
    matchsticks = [5, 5, 5, 5, 16, 4, 4, 4, 4, 4, 3, 3, 3, 3, 4]
    print(Solution().makesquare(matchsticks))
